卢卡斯定理 |
您所在的位置:网站首页 › 组合数 证明 › 卢卡斯定理 |
卢卡斯定理Lucas 定理引入 Lucas 定理用于求解大组合数取模的问题,其中模数必须为素数。正常的组合数运算可以通过递推公式求解(详见 排列组合),但当问题规模很大,而模数是一个不大的质数的时候,就不能简单地通过递推求解来得到答案,需要用到 Lucas 定理。 定义Lucas 定理内容如下:对于质数 ,有 观察上述表达式,可知 和 一定是小于 的数,可以直接求解, 可以继续用 Lucas 定理求解。这也就要求 的范围不能够太大,一般在 左右。边界条件:当 的时候,返回 。 时间复杂度为 ,其中 为预处理组合数的复杂度, 为单次求组合数的复杂度。 实现 1 2 3 4long long Lucas(long long n, long long m, long long p) { if (m == 0) return 1; return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p; } 1 2 3 4def Lucas(n, m, p): if m == 0: return 1 return (C(n % p, m % p, p) * Lucas(n // p, m // p, p)) % p 证明考虑 的取值,注意到 ,分子的质因子分解中 的次数恰好为 ,因此只有当 或 的时候 的质因子分解中含有 ,因此 。进而我们可以得出 注意过程中没有用到费马小定理,因此这一推导不仅适用于整数,亦适用于多项式。因此我们可以考虑二项式 的结果 考虑二项式 ,那么 就是求其在 次项的取值。使用上述引理,我们可以得到 注意前者只有在 的倍数位置才有取值,而后者最高次项为 ,因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值,即在前者部分取 的倍数次项,后者部分取剩余项,即 。 exLucas 定理Lucas 定理中对于模数 要求必须为素数,那么对于 不是素数的情况,就需要用到 exLucas 定理。 过程第一部分:中国剩余定理要求计算二项式系数 ,其中 可能为合数。 考虑利用 中国剩余定理 合并答案,这种情况下我们只需求出 的值即可(其中 为素数且 为正整数)。 根据 唯一分解定理,将 质因数分解: 对于任意 ,有 与 互质,所以可以构造如下 个同余方程: 我们发现,在求出 后,就可以用中国剩余定理求解出 。 第二部分:移除分子分母中的素数根据同余的定义,,问题转化成,求 ( 为质数)的值。 根据组合数定义 ,。 由于式子是在模 意义下,所以分母要算乘法逆元。 同余方程 (即乘法逆元)有解 的充要条件为 (裴蜀定理), 然而 无法保证有解,发现无法直接求 和 , 所以将原式转化为: 表示 中包含多少个 因子, 同理。 第三部分:Wilson 定理的推论问题转化成,求形如: 的值。这时可以利用 Wilson 定理的推论。如果难以理解,可以看看下面的解释。 解释一个示例:22! mod 9 先考虑 , 比如 时: 将其中所有 的倍数提取,得到: 可以看到,式子分为三个整式的乘积: 是 的幂,次数是 ; 是 ,即 ,由于阶乘中仍然可能有 的倍数,考虑递归求解; 是 中与 互质的部分的乘积,具有如下性质: , 即:( 是任意正整数)。 一共循环了 次,暴力求出 ,然后用快速幂求 次幂。 最后要乘上 ,即 ,显然长度小于 ,暴力乘上去。 上述三部分乘积为 。最终要求的是 。 所以有: 于是: 同样是一个数的阶乘,所以也可以分为上述三个部分,于是可以递归求解。 等式的右边两项不含素数 q。事实上,如果直接把 n 的阶乘中所有 q 的幂都拿出来,等式右边的阶乘也照做,这个等式可以直接写成: 式中的 和 都表示把分子中所有的素数 都拿出来。改写成这样,每一项就完全不含 了。 递归的结果,三个部分中,左边部分随着递归结束而自然消失,中间部分可以利用 Wilson 定理的推论 0,右边部分就是推论 2 中的 。 下面这种写法,拥有单次询问 的时间复杂度。其中 int inverse(int x) 函数返回 在模 意义下的逆元。 实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33LL calc(LL n, LL x, LL P) { if (!n) return 1; LL s = 1; for (LL i = 1; i P; i++) if (i % x) s = s * i % P; s = Pow(s, n / P, P); for (LL i = n / P * P + 1; i n; i++) if (i % x) s = i % P * s % P; return s * calc(n / x, x, P) % P; } LL multilucas(LL m, LL n, LL x, LL P) { int cnt = 0; for (LL i = m; i; i /= x) cnt += i / x; for (LL i = n; i; i /= x) cnt -= i / x; for (LL i = m - n; i; i /= x) cnt -= i / x; return Pow(x, cnt, P) % P * calc(m, x, P) % P * inverse(calc(n, x, P), P) % P * inverse(calc(m - n, x, P), P) % P; } LL exlucas(LL m, LL n, LL P) { int cnt = 0; LL p[20], a[20]; for (LL i = 2; i * i P; i++) { if (P % i == 0) { p[++cnt] = 1; while (P % i == 0) p[cnt] = p[cnt] * i, P /= i; a[cnt] = multilucas(m, n, i, p[cnt]); } } if (P > 1) p[++cnt] = P, a[cnt] = multilucas(m, n, P, P); return CRT(cnt, a, p); }若不考虑 excrt 的复杂度,通过预处理 以内的的所有倍数的乘积,可以使时间复杂度优化至单次 。而如果 p 是固定的,我们在一开始就可以对 p 进行分解,并进行预处理,可以达到总复杂度 。 习题Luogu3807【模板】卢卡斯定理SDOI2010 古代猪文 卢卡斯定理Luogu4720【模板】扩展卢卡斯Ceizenpok’s formula本页面最近更新:2023/2/18 07:57:07,更新历史发现错误?想一起完善? 在 GitHub 上编辑此页!本页面贡献者:iamtwz, CornWorld, Enter-tainer, EntropyIncreaser, GitPinkRabbit, Great-designer, Henry-ZHR, Ir1d, ksyx, LuoYisu, Marcythm, MegaOwIer, Menci, ouuan, Sheng-Horizon, SingerCoder, sshwy, Tiphereth-A, TonyYin0418, whongzhong, Xeonacid, YOYO-UIAT本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |